/**
 * 动态规划 问题核心以每个节点为子串结尾 循序遍历一遍 加上下个节点的值 对比就能实现O(n)出结果
 * @param {}} nums 
 */
var maxSubArray = function(nums) {
    //pre 保存改节点为子串结尾的最大结果 
    //max 放置以前出现的最大结果
    var pre=0, max = nums[0];
    nums.forEach((x) => {
        pre = Math.max(pre+x, x);
        max = Math.max(max, pre);
    });
    return max;
}

var maxProfit = function(prices) {
    if(prices.length<=1)return 0;
    var minVal = Math.min(prices[0], prices[1]);
    var max = 0;
    for(var i=1; i<prices.length; i++){
        minVal = Math.min(prices[i], minVal);
        max = Math.max(max, prices[i] - minVal);
    }
    return max;
};
console.log(maxProfit([1]));
console.log(maxProfit([7,1]));
console.log(maxProfit([1,7]));
console.log(maxProfit([7,1,5,3,6,4]));
console.log(maxProfit([7,1,5,3,6,4,2,6,7,8,1,7,9,5,1,1]));
console.log(maxProfit([2,1,2,1,0,1,2]));